package arrAndstr;

/*
	86. 分隔链表
 */
public class T86 {

	public static class ListNode {
		int val;
		ListNode next;

		ListNode() {
		}

		ListNode(int val) {
			this.val = val;
		}

		ListNode(int val, ListNode next) {
			this.val = val;
			this.next = next;
		}
	}

	public static void main(String[] args) {
		ListNode head = new ListNode(1);
		ListNode node = head;

		node.next = new ListNode(4);
		node = node.next;

		node.next = new ListNode(3);
		node = node.next;

		node.next = new ListNode(2);
		node = node.next;

		node.next = new ListNode(5);
		node = node.next;

		node.next = new ListNode(2);

		partition(head, 3);
	}

	public static ListNode partition(ListNode head, int x) {
		if (head == null || head.next == null)	return head;

		// 维护两个链表，一个小于x的，一个大于等于x的
		ListNode small = getSmallHead(head, x);
		ListNode big = getBigHead(head, x);
		if (small == null)	return big;

		ListNode node = small;
		while (true) {
			if (node.next == null) {
				node.next = big;
				break;
			}
			node = node.next;
		}

		return small;
	}

	private static ListNode getBigHead(ListNode head, int x) {
		ListNode node = head;
		ListNode bigHead = new ListNode();
		while (true) {
			if (node == null || node.val >= x) {
				bigHead = node;
				break;
			}
			node = node.next;
		}
		if (bigHead == null)	return null;
		bigHead = new ListNode(node.val);
		ListNode nowHead = node.next;
		node = bigHead;
		while (true) {
			if (nowHead == null)	break;
			if (nowHead.val >= x) {
				node.next = new ListNode(nowHead.val);
				node = node.next;
			}
			nowHead = nowHead.next;
		}
		return bigHead;
	}

	private static ListNode getSmallHead(ListNode head, int x) {
		ListNode node = head;
		ListNode smallHead = new ListNode();
		while (true) {
			if (node == null || node.val < x) {
				smallHead = node;
				break;
			}
			node = node.next;
		}
		if (smallHead == null)	return null;
		smallHead = new ListNode(node.val);
		ListNode nowNode = node.next;
		node = smallHead;
		while (true) {
			if (nowNode == null)	break;
			if (nowNode.val < x) {
				node.next = new ListNode(nowNode.val);
				node = node.next;
			}
			nowNode  = nowNode.next;
		}
		return smallHead;
	}
}
